package com.LeeCode;

/**
 * 分裂二叉树的最大乘积
 */

public class Code1339 {
    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 6};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code1339().maxProduct(root));
    }

    public int sum;
    public int best;

    public int maxProduct(TreeNode root) {
        preOrder(root);
        postOrder(root);
        return (int) (((long) best * (sum - best)) % 1000000007);
    }

    private void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        sum += root.val;
        preOrder(root.left);
        preOrder(root.right);
    }

    private int postOrder(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int cur = postOrder(root.left) + postOrder(root.right) + root.val;
        if (Math.abs(2 * cur - sum) < Math.abs(2 * best - sum)) {
            best = cur;
        }
        return cur;
    }
}
